package com.atwy.recursion;

/**
 * 8皇后问题：
 * 在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，
 * 即：任意两个皇后都不能处于同一行、 同一列或同一斜线上，问有多少种摆法(92)
 * 举例：
 * 1	1   1	8	1	1	1	1
 * 1    8	1	1	1	1	1	1
 * 1	1   1	1	1	1	8	1
 * 1	1   8	1	1	1	1	1
 * 1	1   1	1	1	8	1	1
 * 1	1   1	1	1	1	1	8
 * 1	1   1	1	8	1	1	1
 * 8	1   1	1	1	1	1	1
 * <p>
 * 思路：
 * 我们只需知道第n行的皇后在第几列，然后该皇后与 n-1 个之间不在同行同列同斜线就可以了。
 * 可以用一维数组来表示，比如 {3,1,6,2,5,7,4,0}
 * array[i] = j, i:行, j:列
 * <p>
 * 即一维数组的下标表示二维数组的行（i=0表示第一行，i=1，表示第二行）
 * 一维数组每个下标对应的值表示二维数组的列，（j=0,表示第一列，j=1，表示第二列）
 * <p>
 * 这样我们可以先固定皇后在第一行第一列的位置，然后再确定第二行皇后的位置，依次类推，8皇后确定好之后，
 * 回溯到第一行皇后，将其放在第二列，再往下推。。。
 */
public class Queue8 {
    // 皇后的最大个数
    int max = 8;
    public int[] array = new int[max];
    public static int count; // 记录解法的次数
    public static int judgeCount; // 记录总归经历了多少次冲突

    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.setQueueInPlace(0);// 从第0行的皇后开始

        System.out.printf("一共有%d 解法", count);
        System.out.printf("一共判断冲突的次数%d 次", judgeCount);

    }

    private void setQueueInPlace(int n) {// 放置第n行的皇后
        if (n == max) {
            // 说明皇后已放置好
            print();
            return;
        }
        // 依次放入皇后，判断是否有冲突
        for (int j = 0; j < max; j++) {
            //先把当前第n行的皇后, 放到该行的第 j 列
            array[n] = j;
            //判断当放置第 n 行皇后到 j 列时，是否与前n-1行的皇后冲突
            if (judge(n)) {// 不冲突
                // 接着放n+1个皇后，递归
                setQueueInPlace(n + 1);
            }
        }
    }

    /**
     * 判断当放置第 n 行皇后到 j 列时，是否与前n-1行的皇后冲突
     * @param n
     * @return true: 通过判断，不冲突
     */
    private boolean judge(int n) {
        // 已知 array[n] = j;
        // 1、同行这种情况不用判断，因为本算法就是按行划分皇后的
        // 2、同列, array[i] == array[n],表示在同一列
        // 3、同斜线，在对称的二维棋盘中，同一斜线的斜率k满足 |k| = 1
        // k = (array[i1]-array[i2])/(i1-i2) => |array[n] - array[i]| == |n-i|
        judgeCount++;
        for (int i = 0; i < n; i++) {// i表示行，array[i]表示列
            if (array[i] == array[n] || Math.abs(array[n] - array[i]) == Math.abs(n - i)) {
                return false;
            }
        }
        return true;
    }

    private void print() {
        // 打印组合
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
